home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 9 / CDACTUAL9.iso / share / Dos / VARIOS / pascal / SWAG9605.DDD / 0040_Re: Pascal's triangle.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1996-05-31  |  2.8 KB  |  107 lines
  1. (*
  2.  procedure triangle(x1,x2,y1,y2,z1,z2 : integer);
  3.    begin
  4.      line(x1,x2,y1,y2);
  5.      line(y1,y2,z1,z2);
  6.      line(z1,z2,x1,x2);
  7.    end;
  8.  
  9.  Then just put some coordinates in and .......
  10.  
  11.  use:
  12.  -----
  13.  
  14.  program test;
  15.  
  16.   uses
  17.     crt, graph;
  18.  
  19.   var
  20.     gd, gm : integer;
  21.  
  22.   {the procedure has to be here}
  23.  
  24.  begin
  25.    gd:=detect;
  26.    initgraph(gd,gm,'');
  27.    if graphresult <> grok then halt(1);
  28.  
  29.    triangle(100,200,300,400,50,50);
  30.  
  31.    readln;
  32.    closegraph;
  33.  end.
  34.  
  35.  -------
  36.  
  37. I think the original post was asking for a program to generate Pascal's Triangle.
  38. Pascal's Triangle is a classic example of a recurrence relation that arranges
  39. the binomial coefficients into the shape of a triangle.  The binomial coefficients
  40. are a set of ordered coefficients of the terms in an expansion of a power of a
  41. binomial.  For example:
  42.  
  43.   Binomial     Expanded                              Coefficients
  44. -----------------------------------------------------------------
  45.   (a+b)^0       1                                    1
  46.   (a+b)^1       a + b                                1,1
  47.   (a+b)^2       a^2 + 2ab + b^2                      1,2,1
  48.   (a+b)^3       a^3 + 3(a^2)b + 3a(b^2) + b^3        1,3,3,1
  49.  
  50.  
  51. Here is the top of Pascal's Triangle:
  52.  
  53.            1
  54.           1 1
  55.          1 2 1
  56.         1 3 3 1
  57.        1 4 6 4 1
  58.      1 5 10 10 5 1
  59.            .
  60.            .
  61.            .
  62.  
  63. Note that each position of the triangle holds the sum of the two elements
  64. diagonally above it.  If the positions of each row of the triangle are
  65. 0..n (from left to right) where n is the number of the current row, then
  66. the coefficient values C(row,position) in each position are calculated as
  67. follows:
  68.  
  69.     C(n,0) = 1  and  C(n,n) = 1     For n >= 0
  70.     C(n,k) = C(n-1,k) + C(n-1,k-1)  For n > k > 0
  71.  
  72.  
  73. Since each row of the triangle is dependent on the row immediately above it,
  74. this lends itself nicely to a recursive algorithm:
  75.  
  76. *)
  77.  
  78. FUNCTION CalcCoefficient(CONST n : Integer; CONST k : integer ) : Integer;
  79.   BEGIN
  80.     IF (k=0) or (k=n)
  81.     THEN
  82.       result := 1
  83.     ELSE
  84.       result := CalcCoefficient( n-1, k )  + CalcCoefficient( n-1, k-1 );
  85.   END;
  86.  
  87.  
  88. PROCEDURE GenerateTriangle( CONST maxOrder : INTEGER );
  89.   VAR
  90.     currentCoefficient : Integer;
  91.     order              : integer;
  92.     term               : integer;
  93.   BEGIN
  94.     FOR order := 0 TO maxOrder DO
  95.       FOR term := 0 TO order DO
  96.         BEGIN
  97.           currentCoefficient := CalcCoefficient( order, term );
  98.           { now store, or print the current coefficient - whatever you want }
  99.         END;
  100.   END;
  101.  
  102.  
  103. Note, recursion, as is often he case, is not the most efficient way to generate
  104. Pascal's Triangle.  In this case, each row of the triangle is calculated repeatedl
  105. for every higher order row.  This wastes a trememdous amount of processing.
  106.  
  107.